「提高 - 5C」笛卡尔树

笛卡尔树是一种二叉树，每一个节点由一个键值二元组 $(k, w)$ 构成，竞赛中使用笛卡尔树时，常用数组下标作为二元组的键值 $k$。下面的描述中，均以此为准。

定义

节点的 $k$ 值满足 BST 性质

每个节点的 $k$ 值不小于它的左子树中任意节点的 $k$ 值。
每个节点的 $k$ 值不大于它的右子树中任意节点的 $k$ 值。

即二叉树的中序遍历中，键的顺序一定是从小到大的。

堆性质

节点的权值不小于其子树中所有节点的权值。（或不大于）
权值更大的节点位于更低的层次。

下面是一个具体的由键值对（在序列中的顺序为键）建立笛卡尔树的例子。第一行表示键，第二行表示值。

建树

按照定义建树

1. 找到序列中最小的元素 $1$，该元素作为根节点，$1$ 左边的元素构成了左子树，右边的元素构成了右子树。
2. 递归地以同样的规则分别构建左子树和右子树。

上面建树的时间复杂度为 $O(n^2)$。

利用单调栈建树

观察上图，我们发现每个元素在序列中的先后次序和二叉树中的左右位置是一致的，这提示我们可以按序列中的元素顺序插入新的节点，线性的构建笛卡尔树。

以上图为例，图中的二叉树是已经建立的树，假设当前元素的值为 $x$，$x$ 应该插入到哪个位置呢？要保证中序遍历中 $x$ 最后一个出现，那么 $x$ 一定位于最右侧。但同时维持堆性质，因此，我们采用下面的方法进行调整。

假设 $x = 6$，从下往上检查右链（右链：即从根节点一直往右子树走，经过的节点形成的链），找到第一个小于 $x$ 的节点 $u$。将 $x$ 作为 $u$ 的右儿子，同时原来 $u$ 的右子树作为 $x$ 的左子树。这样便同时维持了 BST 性质和堆性质。

在实现过程中，我们通过一个栈维护右链上的节点，在上面的例子中，栈中存在元素 $1, 5, 7, 9$。当前元素 $x=6$。因此我们检查栈顶元素，若该元素大于 $x$，则弹出栈顶元素。最后将 $6$ 加入栈，得到 $1, 5, 6$ 。这正是单调栈的操作步骤。

stack<int> stk; // 栈用来维护右链上的元素
for (int i = 1; i <= n; i++) { // 遍历序列中的每一个元素
  int lst = 0; // 记录上一个弹出的元素 
  while (!stk.empty() && A[stk.top()] > A[i]) lst = stk.top(), stk.pop();
  if (!stk.empty()) R[stk.top()] = i;
  if (lst) L[i] = lst;
  stk.push(i);
}

运用

1. 区间最小值/最大值查询 RMQ

假设在笛卡尔树中，节点 $x$ 是节点 $l$ 和 $r$ 的最近公公祖先。按照笛卡尔树的性质，我们有以下结论：

• 子树 $x$ 的中序遍历对应原序列中一段连续的区间，$l$ 和 $r$ 在原序列中位于 $x$ 的左右两边。
• $x$ 的值是该区间中最小（或最大）的元素。

由此，我们可以得知，区间 $[l, r]$ 中元素的最小值（最大值）就是 $x$ 的值。也就是说，$\text{LCA}(l, r) = \text{RMQ}(l, r)$。

我们可以利用笛卡尔树处理 RMQ 问题，但在竞赛中，处理 RMQ 问题更多使用 ST 表 和 线段树。通过这里的分析，主要用来帮助理解笛卡尔树的结构。